home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / seg_tree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  8.6 KB  |  316 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  seg_tree.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17.  
  18.  
  19. // ------------------------------------------------------------------
  20. //
  21. // full dynamic Segment Trees
  22. //
  23. // Michael Wenzel     (1990)
  24. //
  25. // Implementation follows
  26. // Kurt Mehlhorn: Data Structures and Algorithms, Vol. 3
  27. //
  28. // ------------------------------------------------------------------
  29.  
  30.  
  31. #ifndef SEGMENTTREEH
  32. #define SEGMENTTREEH
  33.  
  34.  
  35. #include <LEDA/bb_tree.h>
  36. #include <LEDA/list.h>
  37.  
  38. // ------------------------------------------------------------------
  39. // declarations and definitions 
  40. // ----------------------------------------------------------------- 
  41.  
  42.  
  43. class h_segment;
  44. typedef h_segment* h_segment_p;
  45.  
  46. class seg_node_tree;
  47. typedef seg_node_tree* seg_node_list;
  48.  
  49.  
  50. typedef bb_node* seg_tree_item;
  51. declare(list,seg_tree_item);
  52.  
  53. //------------------------------------------------------------------
  54. // class h_segment
  55. //------------------------------------------------------------------
  56.  
  57. class h_segment {
  58.  
  59.   ent _x0;
  60.   ent _x1;
  61.   ent _y;
  62.   ent _inf;
  63.  
  64.  public:
  65.  
  66.  ent& x0()    { return _x0;   }
  67.  ent& x1()    { return _x1;   }
  68.  ent& y()     { return _y;    }
  69.  ent& info()  { return _inf;  }
  70.  
  71.  h_segment()
  72. { 
  73.    _x0 = _x1 = _y = _inf = 0;
  74.  }
  75.  
  76.  h_segment(ent x0, ent x1, ent y, ent i=0)
  77. { 
  78.    _x0  = x0;
  79.    _x1  = x1;
  80.    _y   = y;
  81.    _inf = i;
  82.  }
  83.  
  84. OPERATOR_NEW(4)
  85. OPERATOR_DEL(4)
  86.  
  87.  friend ostream& operator<<(ostream&, h_segment&);
  88.  friend class Segment_Tree;
  89.  friend class seg_node_tree;
  90.  
  91. };
  92.  
  93.  
  94. /*------------------------------------------------------------------
  95.    class seg_node_tree = Dictionary(seg_tree_item , void* )
  96. -------------------------------------------------------------------*/
  97.  
  98. struct seg_node_tree : public bb_tree {
  99.  
  100. Segment_Tree* father;
  101.  
  102. int cmp(ent& x,ent& y) ;
  103.  
  104. list(seg_tree_item) query(ent, ent);
  105. list(seg_tree_item) all_items();
  106.  
  107. int            defined(h_segment_p y)    { return bb_tree::member(Ent(y)); }
  108. seg_tree_item  lookup(h_segment_p y)     { return bb_tree::lookup(Ent(y)); }
  109. seg_tree_item  locate(h_segment_p y)     { return bb_tree::locate(Ent(y)); }
  110. seg_tree_item  ord(int y)                { return bb_tree::ord(int(y)); }
  111. seg_tree_item  insert(h_segment_p y, ent i=0 )
  112.                                  { return bb_tree::insert(Ent(y),i); } 
  113. void del(h_segment_p y)          { delete bb_tree::del(Ent(y)); } 
  114. void del_item(seg_tree_item it)  { del(key(it)); } 
  115.  
  116. h_segment_p& key(seg_tree_item it)   
  117.          { if (!it) error_handler(1,"seg_tree_item gleich nil");
  118.                return (h_segment_p&)it->ke  ; }
  119. ent& info(seg_tree_item it)              { return key(it)->info(); } 
  120. void        change_inf(seg_tree_item it, ent i) { key(it)->info() = i; }
  121.  
  122. seg_node_tree(Segment_Tree* p)   {father = p;}
  123. ~seg_node_tree()  {}
  124.  
  125. friend class Segment_Tree;
  126.  
  127. } ;
  128.  
  129.  
  130. #define forall_seg_tree_items(a,b) for ((b).init_iterator(); a=(b).move_iterator(); )
  131.  
  132.  
  133.  
  134. //------------------------------------------------------------------
  135. // class segment_tree
  136. //------------------------------------------------------------------
  137.  
  138. class Segment_Tree  : public bb_tree {
  139.  
  140.  
  141. virtual  h_segment_p new_y_h_segment(ent y)
  142. { cout << "error: virtual new_y_h_segment\n"; y=0; return 0; }
  143.  
  144. virtual int cmp_dim1(ent& x,ent& y) {return int(x)-int(y);}
  145. virtual int cmp_dim2(ent& x,ent& y) {return int(x)-int(y);}
  146.  
  147. virtual void clear_dim1(ent& x)     { x=0; }
  148. virtual void clear_dim2(ent& x)     { x=0; }
  149. virtual void clear_info(ent& x)     { x=0; }
  150.  
  151. virtual void copy_dim1(ent& x)     { x=x; }
  152. virtual void copy_dim2(ent& x)     { x=x; }
  153. virtual void copy_info(ent& x)     { x=x; }
  154.  
  155. int seg_cmp(h_segment_p p, h_segment_p q);
  156.  
  157.   void lrot(bb_item , bb_item);
  158.   void rrot(bb_item , bb_item);
  159.   void ldrot(bb_item , bb_item);
  160.   void rdrot(bb_item , bb_item);
  161.  
  162.   void change_inf(bb_item it, seg_node_list i)   { info(it) = i; }
  163.   ent& key(bb_item it)       
  164.        { if (!it) error_handler(1,"bb_item in segment_tree gleich nil");
  165.      return it->ke; }
  166.   seg_node_list& info(bb_item it)    { return (seg_node_list&)(bb_tree::info(it)); } 
  167.  
  168.   int start_coord(bb_item& x,seg_tree_item& i)
  169.       { return (!cmp(key(x),x0(i))); }
  170.   int end_coord(bb_item& x,seg_tree_item& i)
  171.       { return (!cmp(key(x),x1(i))); }
  172.  
  173.   int empty(bb_item);
  174.   void clear(bb_item& );
  175.   void print(bb_item , string); 
  176.  
  177.   protected:
  178.  
  179.   seg_node_tree r;                // tree with all segments
  180.  
  181.  
  182.   int cmp_dummy(int a, int b, int c);
  183.  
  184.  
  185.   public :
  186.   
  187.   int cmp(ent& x,ent& y)     
  188.   { cout << "error: Segment_Tree::cmp\n"; x=y=0; return 0; }
  189.  
  190.   ent x0(seg_tree_item x)    { return (r.key(x))->_x0;  }
  191.   ent x1(seg_tree_item x)    { return (r.key(x))->_x1;  }
  192.   ent y(seg_tree_item x)     { return (r.key(x))->_y;   }
  193.   ent& inf(seg_tree_item x)  { return r.info(x);        }
  194.  
  195.   ent& x0(h_segment_p x)   { return x->_x0; }
  196.   ent& x1(h_segment_p x)   { return x->_x1; }
  197.   ent& y(h_segment_p x)    { return x->_y; }
  198.   ent& inf(h_segment_p x)  { return x->_inf; }
  199.  
  200.   void change_inf(seg_tree_item x, ent i)  { r.info(x) = i; }
  201.  
  202.   seg_tree_item insert(ent, ent, ent, ent i=0 );
  203.  
  204.   void del(ent, ent, ent);
  205.   void del_item(seg_tree_item it) { del(x0(it),x1(it),y(it)) ; }
  206.  
  207.  
  208.   seg_tree_item lookup(ent, ent, ent );
  209.   int member(ent x0, ent x1, ent y) { return (lookup(x0,x1,y)!=0 ) ; }
  210.  
  211.   list(seg_tree_item) query(ent, ent, ent );
  212.   list(seg_tree_item) x_infinity_query(ent, ent );
  213.   list(seg_tree_item) y_infinity_query(ent );
  214.   list(seg_tree_item) all_items();
  215.  
  216.   void clear_tree();  
  217.  
  218.    Segment_Tree();
  219.   ~Segment_Tree();
  220.  
  221.   int size()                   { return r.size();   }
  222.   int empty()                  { return (r.size()==0) ; }
  223.  
  224.   seg_tree_item y_min()        { return r.min();    }
  225.   seg_tree_item y_max()        { return r.max();    }
  226.  
  227.   void init_iterator()            { r.init_iterator(); }
  228.   seg_tree_item move_iterator()   { return r.move_iterator(); }
  229.  
  230.   void print_tree()               { print(root,"");    }
  231.  
  232.  
  233.   friend class seg_node_tree;
  234.  
  235. };
  236.  
  237.  
  238. //------------------------------------------------------------------
  239. // typed segment_tree
  240. //------------------------------------------------------------------
  241.  
  242. #define segment_tree(type1,type2,itype) name4(type1,type2,itype,segment_tree)
  243.  
  244. #define segment_treedeclare3(type1,type2,itype)\
  245. \
  246. struct segment_tree(type1,type2,itype) : public Segment_Tree {\
  247. \
  248. h_segment_p new_y_h_segment(ent y)\
  249. { type1 x1;\
  250.   type2 x2;\
  251.   return new h_segment(Copy(x1),Copy(x2),y);\
  252.  }\
  253. \
  254. int cmp_dim1(ent& x,ent& y) { return compare(*(type1*)&x,*(type1*)&y); }\
  255. int cmp_dim2(ent& x,ent& y) { return compare(*(type2*)&x,*(type2*)&y); }\
  256. \
  257. void clear_dim1(ent& x)     { Clear(*(type1*)&x); }\
  258. void clear_dim2(ent& x)     { Clear(*(type2*)&x); }\
  259. void clear_info(ent& x)     { Clear(*(itype*)&x); }\
  260. \
  261. void copy_dim1(ent& x)     { x = Copy(*(type1*)&x); }\
  262. void copy_dim2(ent& x)     { x = Copy(*(type2*)&x); }\
  263. void copy_info(ent& x)     { x = Copy(*(itype*)&x); }\
  264. \
  265. int cmp(ent& x,ent& y)      { return compare((type1&)x,(type1&)y); }\
  266. \
  267. type1  x0(seg_tree_item it)  { return type1(Segment_Tree::x0(it)); }\
  268. type1  x1(seg_tree_item it)  { return type1(Segment_Tree::x1(it)); }\
  269. type2   y(seg_tree_item it)  { return type2(Segment_Tree::y(it));  }\
  270. itype inf(seg_tree_item it)  { return itype(Segment_Tree::inf(it));}\
  271. \
  272. seg_tree_item insert(type1 x0, type1 x1, type2 y, itype i)\
  273. { return Segment_Tree::insert(Ent(x0),Ent(x1),Ent(y),Ent(i)); }\
  274. \
  275. void del(type1 x0, type1 x1, type2 y)\
  276. { Segment_Tree::del(Ent(x0),Ent(x1),Ent(y)); }\
  277. \
  278. seg_tree_item lookup(type1 x0, type1 x1, type2 y)\
  279. { return Segment_Tree::lookup(Ent(x0),Ent(x1),Ent(y)); }\
  280. \
  281. int member(type1 x0, type1 x1, type2 y)\
  282. { return Segment_Tree::member(Ent(x0),Ent(x1),Ent(y)); }\
  283. \
  284. list(seg_tree_item) query(type1 x,type2 y0,type2 y1)\
  285. { return Segment_Tree::query(Ent(x),Ent(y0),Ent(y1)); }\
  286. \
  287. list(seg_tree_item) x_infinity_query(type2 y0,type2 y1)\
  288. { return Segment_Tree::x_infinity_query(Ent(y0),Ent(y1)); }\
  289. \
  290. list(seg_tree_item) y_infinity_query(type1 x)\
  291. { return Segment_Tree::y_infinity_query(Ent(x)); }\
  292. \
  293. \
  294. segment_tree(type1,type2,itype)()  {}\
  295. ~segment_tree(type1,type2,itype)()\
  296.  { seg_tree_item z;\
  297.   forall_seg_tree_items(z,r)\
  298.   { Clear(x0(z)); \
  299.     Clear(x1(z)); \
  300.     Clear(y(z)); \
  301.     Clear(inf(z)); \
  302.     delete r.key(z); }\
  303.  }\
  304. \
  305. } ;
  306.  
  307.  
  308. //------------------------------------------------------------------
  309. // Iterator
  310. //------------------------------------------------------------------
  311.  
  312. #define forall_seg_tree_items(a,b) for ((b).init_iterator(); a=(b).move_iterator(); )
  313.  
  314.  
  315. #endif
  316.